package com.qz.stack.calculator;

import com.qz.util.CalculatorUtils;

import java.util.*;


/**
 * @Description 逆波兰表达式
 * @Author Flag
 * @Date: 2021/7/24 10:50
 * @Version: 1.0
 **/
public class PolandNotationDome {
    public static void main(String[] args) {
//        //定义逆波兰表达式
//        String suffixExpression = "1 2 3 * + 4 5 * + 6 -";
//        //1.先将逆波兰表达式放到ArrayList中
//        List<String> rpnList = getListString(suffixExpression);
//        //2.将ArrayList传入一个方法，遍历ArrayList配合栈，得出结果
//        int calculate = calculate(rpnList);
//        System.out.println(calculate);

        String expression = "1+((2+3)*4)-5";
        List<String> strings = toInfixExpressionList(expression);
        System.out.println(strings);

        System.out.println("结束");
        List<String> strings1 = parseSuffixExpressionList(strings);
        System.out.println(strings1);

    }

    /**
     * 将一个逆波兰表达式，一次将数据和运算符放入到ArrayList中
     * @param suffixExpression
     * @return
     */
    public static List<String> getListString(String suffixExpression){
        //将suffixExpression分割
        String[] split = suffixExpression.split(" ");
        return Arrays.asList(split);
    }

    /**
     * 1)从左至右扫描，将3和4压入堆栈;将3和4压入堆栈;
     * 2)遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈;
     * 3)将5入栈;
     * 4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈;
     * s)将6入栈;
     * 6)最后是-运算符，计算出 35-6的值，即29，由此得出最终结果
     * 完成对逆波兰表达式的运算
     * @param list
     * @return
     */
    public static int calculate(List<String> list){
        //创建一个栈，只需要一个栈即可
        Stack<String> stack = new Stack<>();
        //遍历集合
        for (String item : list) {
            //使用正则表达式判断是否是数字
            if(item.matches("\\d+")){
                //入栈
                stack.push(item);
            } else {
                //出栈两个数，计算后在入栈
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());

                int cal = CalculatorUtils.cal(num1, num2, item.charAt(0));

                stack.push(cal+"");


            }

        }
        //最后留在栈中的数据就是运算结果
        return Integer.parseInt(stack.pop());
    }


    //完成将一个中缀表达式转成后缀表达式的功能
    //说明,
    //因为直接对str进行操作，不方便，因此，先将字符串转成List
    public static List<String> toInfixExpressionList(String s){
        //定义一个集合，用来存储结果
        List<String> ls = new ArrayList<>();
        //定义一个List,存放中缀表达式对应的内容
        int index = 0;
        //定义一个builder，用来存储多位数的值
        StringBuilder keepString = new StringBuilder();
        //遍历每一个字符，都放入到c
        char c;
        //遍历每一个元素，直到结束
        while (index < s.length()){
            //获取到低index的字符
            c = s.charAt(index);
            //判断当前字符是否是数字
            if(CalculatorUtils.isNumber(c)){
                //如果是数字，需要判断是否是多位数
                //循环遍历下一个，条件：1.没有超出总长度,2.下一个依旧是数字
                while (index < s.length() && CalculatorUtils.isNumber(c= s.charAt(index))){
                    //追加到字符中
                    keepString.append(c);
                    //移动坐标到下雨给
                    index++;
                }
                //添加到集合中
                ls.add(keepString.toString());
                //清空缓冲区s
                keepString.delete(0,keepString.length());
            } else {
                //如果不是一个数字
                ls.add(c+"");
                index++;
            }
        }
        return  ls;
    }


    /**
     * 1.初始化两个栈，运算符栈s1和存储中间结果的栈s2
     * 2.从左至右扫描中缀表达式
     * 3.遇到操作数，将其压入s2
     * 4.遇到运算符时，比较其与s1栈顶运算发的优先级：
     * 4.1.如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符压入s1栈
     * 4.2.否则，若优先级比栈顶运算符高，也将运算符压入s1
     * 4.3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中的栈顶运算符相比较
     * 5.遇到括号时
     * 5.1如果是左括号“（”，直接压入s1
     * 5.2.如果是右括号“）”，则一次弹出s1栈顶的运算符，并压入s2，知道遇到左括号为止，此时将这一对括号丢掉
     * 6.重复步骤2到5，知道表达式的最右边
     * 7.将s1中剩余的运算符一次弹出并压入s2
     * 8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     * @param ls
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> ls){
        //1.初始化两个栈
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        //2.从左至右开始扫描中缀表达式
        for (String item : ls) {
            //如果是数字，直接压入s2
            if(item.matches("\\d+")){
                s2.add(item);
            } else {
                if(s1.isEmpty() || CalculatorUtils.isLeftBracket(item)){
                    //如果s1为空,或者是左半括号，直接入栈
                    s1.push(item);
                } else if(CalculatorUtils.isRightBracket(item)){
                    //如果是右半括号
                    //直到找到与当前括号相同基本的坐标括号
                    while (CalculatorUtils.bracketEquals(item) != CalculatorUtils.bracketEquals(s1.peek())){
                        String pop = s1.pop();
                        s2.add(pop);
                    }
                    //消除左侧的小括号
                    String pop = s1.pop();
                } else{
                    //当item的优先级小于等于s1栈顶运算符，讲s1栈顶的运算符弹出并加入到s2中，在次转到4.1中与s1中新的运算符比较
                    // 问题：缺少一个比较优先级高低的方法
                    while (!s1.isEmpty()  && CalculatorUtils.priority(item) <=  CalculatorUtils.priority(s1.peek())){
                        String pop = s1.pop();
                        s2.add(pop);
                    }
                    //还需要讲item压入栈中
                    s1.push(item);
                }
            }
        }

        //7.将s1中剩余的运算符一次弹出并压入s2
        while (!s1.isEmpty()){
            String pop = s1.pop();
            s2.add(pop);
        }

        //8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
        return s2;




    }


}
